public class Offer44 {
    //    public int findNthDigit(int n) {
//        if (n==0){
//            return 0;
//        }
//        StringBuilder stringBuilder = new StringBuilder();
//        for (int i = 0; i <=n ; i++) {
//            if (stringBuilder.length()<n){
//                stringBuilder.append(String.valueOf(i));
//            } else {
//                return stringBuilder.charAt(n-1)-'0';
//            }
//        }
//        return 0;
//    }
    public int findNthDigit(int n) {
        if (n < 0) {
            return -1;
        }
        int digits = 1;
        while (true) {
            int numbers = countOfInteger(digits);
            if (n < (long)digits * numbers) {
                return digitAtIndex(n, digits);
            }
            n -= digits * numbers;
            digits++;
        }
    }

    private int digitAtIndex(int n, int digits) {
        int number = beginNumber(digits) + n / digits;
        int indexRight = digits - n % digits;
        for (int i = 1; i < indexRight; i++) {
            number /= 10;
        }
        return number % 10;
    }

    private int beginNumber(int digits) {
        if (digits == 1) {
            return 0;
        }
        return (int) Math.pow(10, digits - 1);
    }

    private int countOfInteger(int digits) {
        if (digits == 1) {
            return 10;
        }
        int count = (int) Math.pow(10, digits - 1);
        return 9 * count;
    }

    public static void main(String[] args) {
        Offer44 offer44 = new Offer44();
        System.out.println(offer44.findNthDigit(1000000000));
    }
}
